//sgu 206
/*****上面那份比较好敲*****下面的这份km速度比上面快*********/
/*************km模板最大权匹配****************************/
const int maxn = 100;//n的总点数,0到n-1,n是少的点，m是多的点
const int maxm = 502;//m的总点数,0到m-1,右边的点从0开始完全没有问题
int ux[maxn],lx[maxn];//ux，uy表示x或y是否用过
int uy[maxm],ly[maxm];//lx[i]+ly[j]=mat[i][j]这是km的定理
int to[maxm], mat[maxn][maxm];
int findPath(int i,int s)
{
    ux[i] = 1;
    for (int j = 0; j < s; j++)
    if (!uy[j] && lx[i] + ly[j] == mat[i][j])
    {
        uy[j] = 1;
        if (to[j] == -1 || findPath(to[j],s))
        {
            to[j] = i;
            return 1;
        }
    }
    return 0;
}
inline int KM(int n, int m, int mat[][maxm]) 
{	
	int i,j,k,del;
	memset(to, -1, sizeof(to));
    memset(lx, 0, sizeof(lx));
    memset(ly, 0, sizeof(ly));
    for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
           lx[i] = max(lx[i], mat[i][j]);
    for ( k = 0; k < n; k++)
    while (1)
    {
        memset(ux, 0, sizeof(ux));
        memset(uy, 0, sizeof(uy));
        if (findPath(k,m)) break;
        del = inf;
        for ( i = 0; i < n; i++)
            if (ux[i])
                for ( j = 0; j < m; j++)
                    if (!uy[j])
                    del = min(del, lx[i] + ly[j] - mat[i][j]);
        if (del == 0 || del == inf) break;
        for ( i = 0; i < n; i++)
            if (ux[i])
                lx[i] -= del;
        for ( i = 0; i < m; i++)
            if (uy[i])
                ly[i] += del;
    }
}
/*************km模板****************************/

int m, n,cnt;
int pre[maxn],use[maxn],too[maxn];
struct edge
{
	int u,v,w;
	edge(){}
	edge(int a,int b,int c){
		u=a; v=b; w=c;
	}
}a[maxv];
int g[maxn][maxn];

bool dfs(int now,int f,int pre,int id)
{
	if(now==f)	return true;
	for(int i=1; i<=n; i++)
	if(i!=pre && g[now][i]!=-1)
	{
		if(dfs(i,f,now,id))
		{
			mat[g[now][i]-1][id-n]=a[g[now][i]].w-a[id].w;
			return true;
		}
	}
	return false;
}
int main() 
{

    int i,j,t,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
	N=n;M=m;
    	memset(too,0,sizeof(too));
    	memset(a,0,sizeof(a));
     	memset(g,-1,sizeof(g));
    /*************km模板****************************/
		memset(mat, 0, sizeof(mat));//这个地方时不时要清空,0到n-1的问题
	/*************km模板****************************/
       	int x,y,z;
       	for(i=1;i<=m; i++)
       	{
       		scanf("%d%d%d",&x,&y,&z);
			a[i]=edge(x,y,z);
			len[i]=z;
       	}
		for(i=1; i<n; i++)
		{
			g[a[i].u][a[i].v]=g[a[i].v][a[i].u]=i;
		}
		for(i=n; i<=m; i++)
		{
			 dfs(a[i].u,a[i].v,-1,i);
		}
	
		k=max(m-n+1,n-1);
        /*************km模板****************************/
        int tp=KM(n-1,k,mat);//求km,n是少的点，m是多的点
        /*************km模板****************************/
		 
			   i=1;
		for(j=0; j<N-1; j++)
		{
			len[i]-=lx[j];
			i++;
		}
		for(j=0; j<M-N+1; j++)
		{
			len[i]+=ly[j];
			i++;
		}
    	for(i=1; i<=m; i++)
    	{
    		printf("%d\n",len[i]);
    	}
    }
    return 0;
}


/*****上面那份比较好敲*****下面的这份km速度比上面快*********/
//poj 3638 非常好的题，而且左右点不相同
const int inf = 1012345678;
/*************km模板最大权匹配****************************/
const int maxn = 502;//n的总点数,0到n-1,n是少的点，m是多的点
const int maxm = 502;//m的总点数,0到m-1,右边的点从0开始完全没有问题
int t[maxm],l2[maxm], match2[maxm];//分清楚是maxm
int s[maxn],l1[maxn], match1[maxn];//是maxn
inline int KM(int n, int m, int mat[][maxm]) 
{
    int  p, q, ret = 0, i, j, k;
    for (i = 0; i < n; i++) 
    {
        l1[i] = -inf;
        for (j = 0; j < m; j++) 
        {
            l1[i] = mat[i][j] > l1[i] ? mat[i][j] : l1[i];
        }
    }
    for (i = 0; i < m; l2[i++] = 0);
    memset(match1,-1,sizeof(match1));//-1
    memset(match2,-1,sizeof(match2));//-1
    for (i = 0; i < n; i++) 
    {
        memset(t,-1,sizeof(t));//-1
        for (s[p = q = 0] = i; p <= q && match1[i] < 0; p++) 
        {
            k = s[p];
            for (j = 0; j < m && match1[i] < 0; j++) 
                if (l1[k] + l2[j] == mat[k][j] && t[j] < 0)
                 {
                    s[++q] = match2[j];
                    t[j] = k;
                    if (s[q] < 0) 
                    {
                        for (p = j; p >= 0; j = p) 
                        {
                            match2[j] = k = t[j];
                            p = match1[k];
                            match1[k] = j;
                        }
                    }
                }
        }
        if (match1[i] < 0) 
        {
            i--;
            p = inf;
            for (k = 0; k <= q; k++) 
            for (j = 0; j < m; j++) 
            if (t[j] < 0 && l1[s[k]] + l2[j] - mat[s[k]][j] < p) 
                        p = l1[s[k]] + l2[j] - mat[s[k]][j];
            for (j = 0; j < m; j++) 
                l2[j] += t[j] < 0 ? 0 : p;
            for (k = 0; k <= q; k++) 
                l1[s[k]] -= p;
        }
    }
    for (i = 0; i < n; i++) 
        ret += mat[i][match1[i]];
    return ret;
}
/*************km模板****************************/
int m, n, mat[110][maxm];
int g[110][maxm];
int main() 
{
    int i,j,t,k;
    scanf("%d",&t);
    while(t--)
    {
    /*************km模板****************************/
		memset(mat, 0, sizeof(mat));
	/*************km模板****************************/
     	scanf("%d%d",&n,&m);   
        for(i=0;i<n; i++)
        for(j=0; j<m; j++)
            scanf("%d", &g[i][j]);
        int cnt=0;
        int mm;
		for(i=0; i<n; i++)
		{
			cnt=0;
			for(j=0; j<m; j++)
			{
				for(k=1; k<=n; k++)
				{
					mat[i][cnt++]=-k*g[i][j];
				}		
			}
			mm=cnt;
		}
        /*************km模板****************************/
        int a=KM(n,mm,mat);//求km,n是少的点，m是多的点
        /*************km模板****************************/
		double res=(double)a/n;
        printf("%.6lf\n",-res);
    }
    return 0;
}

